package 剑指offer;

import org.junit.Test;

public class _36二叉搜索树与双向链表 {
	@Test
	public void test() {
		Node nod1=new Node(4,new Node(2),new Node(5));
		nod1.left.left =new Node(1);
		nod1.left.right =new Node(3);
		
		
	}
	/**
	 * 
	 *@time 2021年3月3日下午10:03:02
	 * 
	 *@param root
	 *@return Node
	 *
	 *@see 由图可知是中序遍历
	 */
	Node pre,head;
    public Node treeToDoublyList(Node root) {
    	if(root==null) return null;
    	recur(root);
    	pre.right = head;
    	head.left =pre;   	
		return head;
        
    }
    public void recur(Node node) {
    	if(node == null) return;
		recur(node.left);
		
		if(pre != null) {
			pre.right = node;
			node.left = pre;
		}
		else  head = node;
		pre = node;		
		recur(node.right);
	}
	class Node {
		public int val;
		public Node left;
		public Node right;

		public Node() {}

		public Node(int _val) {
			val = _val;
		}

		public Node(int _val,Node _left,Node _right) {
			val = _val;
			left = _left;
			right = _right;
		}
	}
};
